Three-dimensional (3D) graphics systems are becoming more common on low-cost and portable personal computer (PCs). The surfaces of 3D objects are approximated as triangles that are transformed and displayed from the user's perspective. Often a repeating pattern or texture is applied to these surfaces for added realism.
The texture is stored in texture maps of varying levels of detail (LOD). Object surfaces closer to the user are shown in more detail by using a texture map with a high LOD, while far-away surfaces are shown with little texture detail by using a texture map with a coarser LOD. The texture pixels (texels) in the texture map are used to modify or modulate the pixels being displayed for the triangle to add the texture to the triangle.
FIG. 1 shows texture maps with three different levels-of detail. The LOD=3 map is an 8.times.8 texture map with 8 rows of 8 texels; a total of 64 texels. This level of detail may be used for surfaces at some distance to the viewer. The LOD=2 map has only 4.times.4 or 16 texels. Each texel in the 4.times.4 map may be generated by averaging together four pixels in the 8.times.8 map.
The coarsest level map is a 1.times.1 LOD0 map with only one texel. The LOD0 map is generated from the LOD=1 map by `averaging` together groups of pixels in the 2.times.2 map for each texel in the 1.times.1 map. The LOD=0 map is used for more distant object surfaces that show little surface-texture detail.
When the triangle is parallel to the viewer so that all pixels are nearly the same distance (depth) from the viewer, the texels on a single LOD map can be applied directly to the pixels from a single LOD map. However, as triangles rotate with respect to the viewer, some pixels on the triangle are at a greater distance from the viewer than others. Perspective correction is required when using linear interpolation rasterization.
The u,v coordinate values calculated may not be exact integer values. The pixel may fall between texels on the texture map. Then the texture value for the pixel may be calculated by a distance-weighted average of the four closest texels to the exact u,v coordinate. This is known as bi-linear interpolation since interpolation is performed linearly in each of the two dimensions of a single LOD texture map.
The LOD map selected depends on the rate of change or derivative of the u,v values with respect to the x and y pixel coordinates. Triangles at high or glancing angles to the viewer have many u,v points per screen pixel (x and y values) and thus have at least one high derivative of u,v with respect to x,y. The largest of the four derivatives (du/dx, dv/dx, du/dy, dv/dy) may be used to determine the LOD map to select for a pixel, although more correct methods may be used.
LOD Map Selection--FIG. 2
FIG. 2 is a graph showing selection of LOD maps using derivatives. LOD map 10 is the finest-detail map, having 2.sup.10.times.2.sup.10 texels, or 1024.times.1024. The coarsest map, LOD 0, has only one texel (2.sup.0.times.2.sup.0 or 1.times.1). The largest of the four derivatives of texture-space coordinates u,v with respect to screen coordinates x,y is used to select which LOD map to use. For example, when the largest derivative is 2.sup.9 or more, the coarsest map, LOD 0, is selected. When the largest derivative is less than 2.sup.0 or 1, then the finest-detail map is used, LOD 10.
The LOD-transition function shown by steps 10 is a step function. As the largest derivative doubles, the next-coarser LOD map is selected. For example, derivatives of 2.sup.4 to 2.sup.5 -1 use LOD 5, a 2.sup.5.times.2.sup.5 (32.times.32) map. Once the derivative reaches 25, the next-coarser LOD map is chosen. The abrupt transition from one LOD map to the next can sometimes be seen as a sudden change from a sharp image to a less sharp image. In real-time, this appears as a wave--several may be visible at different ranges--moving across the data base as the viewer moves across the data base.
Bi-linear interpolation is inadequate since abrupt, noticeable changes in image sharpness can occur as the next LOD map is selected. To eliminate these artifacts, tri-linear interpolation is often used. Tri-linear interpolation performs bi-linear interpolation for 2 adjacent LOD maps. Four texels on one LOD map are averaged to produce a first bi-linear result for one LOD map, and then four texels on an adjacent LOD map are averaged to produce a second bi-linear result. The first and second bi-linear results are then linearly interpolated. The interpolation factor is the complement of the fraction of the largest derivative value.
FIG. 3 is a graph showing LOD `smoothing` using tri-linear interpolation. The texel results from two adjacent LOD maps are linearly interpolated for tri-linear interpolation.
For bi-linear interpolation, the LOD-transition function is shown by steps 10 is a step function. With tri-linear interpolation, a weighted average of the two adjacent LOD maps is used to produce texel values. For example, when the largest derivative is 6, the texture map for LOD 7 is used for bi-linear interpolation. Tri-linear interpolation also selects the next-coarser LOD map, LOD 6. The bi-linear average of the four adjacent texels on LOD 6 is then averaged with the LOD 7 average to produce the tri-linear result. This result falls on the tri-linear line 12.
Tri-linear line 12 thus smoothes out the abrupt steps 10 of bi-linear interpolation. Texels from two LOD maps are averaged. This improves image quality by eliminating the noticeable changes in level-of-detail. However, tri-linear interpolation produces some blurring of the image, and also increases the complexity of the calculations required by the graphics engine.
Kamen et al., U.S. Pat. No. 5,812,141, discloses an adaptive texture-mapping controller. Different interpolation methods are used based on the hierarchical level (primitive, span, pixel) and control signals. Economy et al., U.S. Pat. No. 5,367,615, describes a smoothing scheme for providing finer detail based on the polygon density. Yang, U.S. Pat. No. 5,719,599, describes a method for providing more effective scanning of textured surfaces. While useful, a better scheme for smoothing LOD transitions and reducing complexity is desired.
What is desired is a 3D graphics system that adapts the interpolation method. It is desired to reduce computational complexity when using tri-linear interpolation. It is desired to dynamically use either bi-linear or tri-linear interpolation. It is desired to smooth the abrupt bi-linear transitions from one LOD to another LOD. It is further desired to use tri-linear interpolation only near LOD transitions, while using bi-linear interpolation when the LOD is not near a transition.